package lc.q300_350;

public class Q303 {

    public static void main(String[] args) {
        NumArray numArray = new NumArray(new int[]{
                -2, 0, 3, -5, 2, -1
        });
        System.out.println(numArray.sumRange(0, 2));
        System.out.println(numArray.sumRange(2, 5));
        System.out.println(numArray.sumRange(0, 5));
    }

    public static class NumArray {
        int[] nums;

        Integer[] sums;

        int maxI = -1;

        public NumArray(int[] nums) {
            this.nums = nums;
            sums = new Integer[nums.length];
//            getPartSum(nums.length - 1);
        }

        private int getPartSum(int i) {
            if (i < 0) {
                return 0;
            }
            if (maxI < i) {
                // 则遍历计算
                int sum = 0;
                if (maxI >= 0) {
                    sum = sums[maxI];
                }
                for (int j = maxI + 1; j <= i; j++) {
                    sum += nums[j];
                    sums[j] = sum;
                }
                maxI = i;
            }
            return sums[i];
        }

        public int sumRange(int left, int right) {
            // 将前n位记录到数组中
            return getPartSum(right) - getPartSum(left - 1);
        }
    }

}
